package com.example.leetcode.prcatice;

// [1,0,2,3,4]
// 1,0,3,2,4
// 0,1,2,3,4

/**
 * 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
 *
 * 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
 *
 * 返回数组能分成的最多块数量。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test769 {


    public int maxChunksToSorted(int[] arr) {
         // 其实贪心算法，按照题意如果遍历到i的位置可以分块，那么前i的位置的最大值肯定为i,不然肯定有比较小的值在后面了，不满足题意了
        int res = 0;
        int max = 0;
        for (int i = 0;i<arr.length; i++) {
            max = Math.max(max,arr[i]);
            if (max == i) {
                res++;
            }
        }
        return res;
    }
}
